﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    public class T_0021_MergeTwoLists
    {
        // 合并两个有序链表

        // 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

        // 提示：
        //   两个链表的节点数目范围是[0, 50]
        //   -100 <= Node.val <= 100
        //   l1 和 l2 均按 非递减顺序 排列

        public void Test()
        {
            var l1 = new ListNode(2)
            {
                next = new ListNode(5)
                {
                    next = new ListNode(7)
                }
            };
            var l2 = new ListNode(1)
            {
                next = new ListNode(4)
            };
            var result = MergeTwoLists(l1, l2);
            while (result != null)
            {
                Console.WriteLine(result.val);
                result = result.next;
            }
            Console.Read();
        }

        // 257
        // 16
        public ListNode MergeTwoLists(ListNode l1, ListNode l2)
        {
            if (l1 == null || l2 == null)
                return l1 ?? l2;
            var result = l1.val > l2.val ? l2 : l1;
            while (l1 != null || l2 != null)
            {
                ListNode temp1 = l1.next;
                ListNode temp2 = l2.next;
                if (l1.next.val > l2.next.val)
                {
                    l2.next = l1;
                }
                else
                {
                    l1.next = l2;
                }
                if (temp1 == null)
                {
                    l1.next = temp2;
                    break;
                }
                if (temp2 == null)
                {
                    l2.next = temp1;
                    break;
                }
                l1 = temp1;
                l2 = temp2;
            }
            return result;
        }

        public ListNode MergeTwoLists1(ListNode l1, ListNode l2)
        {
            if (l1 == null)
                return l2;
            if (l2 == null)
                return l1;
            var stack = new Stack<ListNode>();
            while (l1 != null || l2 != null)
            {
                if (l2 == null || (l1 != null && l1.val < l2.val))
                {
                    stack.Push(l1);
                    l1 = l1.next;
                }
                else
                {
                    stack.Push(l2);
                    l2 = l2.next;
                }
            }
            var result = stack.Pop();
            while (stack.Count > 0)
            {
                var temp = stack.Pop();
                temp.next = result;
                result = temp;
            }
            return result;
        }

        // 递归
        public ListNode MergeTwoLists2(ListNode linked1, ListNode linked2)
        {
            //只要有一个为空，就返回另一个
            if (linked1 == null || linked2 == null)
                return linked2 ?? linked1;
            //把小的赋值给first
            ListNode first = (linked2.val < linked1.val) ? linked2 : linked1;
            //first.next = MergeTwoLists2(first.next, first == linked1 ? linked2 : linked1);
            first.next = MergeTwoLists2(first.next, linked2.val < linked1.val ? linked1 : linked2);
            return first;
        }

    }
}
